package com.classicalAlgorithm.shuffle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class Solution {
    // 得到一个在闭区间 [min, max] 内的随机整数
    private int randInt(int min, int max) {
        Random r1 = new Random();
        return r1.nextInt(max - min + 1) + min;
    }

    ;

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void shuffle(int[] arr) {
        int len = arr.length;

        //  关键部分
        for (int i = 0; i < len; i++) {
            // 从i到最后, 即[i, len-1]随机选取一个元素
            int rand = randInt(i, len - 1);
            swap(arr, i, rand);
        }
    }

    public void shuffle02(int[] arr) {
        int len = arr.length;

        //  关键部分
        for (int i = 0; i < len - 1; i++) {
            // 从i到最后, 即[i, len-1]随机选取一个元素
            int rand = randInt(i, len - 1);

            swap(arr, i, rand);
        }
    }

    public void shuffle03(int[] arr) {
        int len = arr.length;

        //  关键部分
        for (int i = len - 1; i >= 0; i--) {
            // 从i到最后, 即[i, len-1]随机选取一个元素
            int rand = randInt(0, i);
            swap(arr, i, rand);
        }
    }

    public void shuffle04(int[] arr) {
        int len = arr.length;

        //  关键部分
        for (int i = len - 1; i > 0; i--) {
            // 从i到最后, 即[i, len-1]随机选取一个元素
            int rand = randInt(0, i);
            swap(arr, i, rand);
        }
    }


    public static void main(String[] args) {
//        int[] test = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        Solution s1 = new Solution();
//        s1.shuffle(test);
//
//        System.out.print(Arrays.toString(test));
//
        // 蒙特卡罗
        int N = 1000000;
        HashMap<String, Integer> count = new HashMap<String, Integer>(); // 作为直方图

        for (int i = 0; i < N; i++) {
            int[] arr = {1, 2, 3};
            s1.shuffle(arr);

            String res = Arrays.toString(arr);
            // 此时 arr 已被打乱

            if(!count.containsKey(res)){
                count.put(res, 0);
            }
            int counter = count.get(res);
            count.put(res, counter+1);
        }


        for (int feq : count.values()){
            double res = (double)feq/N;
            System.out.print( res + " "); // 频率
        }

    }
}
